package L628;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: javase
 * @description:
 * @author: luolidong
 * @create: 2021-06-30 09:02
 * @version: 1.0
 */
public class PrimeNum {
    public List<Integer> find1(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        boolean flag = true;
        for (int i = 3; i <= n; i++) {
            for (int j = i - 1; j > 1; j--) {
                if (i % j == 0) {
                    flag = false;
//                    break;
                }
            }
            if (flag) list.add(i);
            flag = true;
        }
        return list;
    }

    public List<Integer> find2(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        boolean[] nums = new boolean[n + 1];
        Arrays.fill(nums, true);
        for (int i = 2; i*i <= n; i++) {
            //判断nums[i]为质数，才把他的倍数置为false
            if(nums[i]==true){
                for (int j = i * i; j<= n; j += i) {
                    nums[j] = false;
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (nums[i]) list.add(i);
        }
        return list;
    }

    public static void main(String[] args) {
        List<Integer> list = new PrimeNum().find2(100);
        System.out.println(list);

    }
}
